
def FindMedian_Recur(A, B, n):
    """
    注意，本题的特殊性在于，A和B的长度都是n，所以，子问题仍是求两个长度相同的数组的
    中位数。在一般的问题中，A，B长度不同，故原问题是求中位数，到了子问题就是求第K小了，
    并且K值会变化。并且，由于特殊性，每次可以把数据规模减半，使得子问题仍是两个长度相等的数组。

    但是本题的参考答案是不正确的，因为实际上，中位数可能只在其中一个数组（比如说A），这样，势必另一个
    数组会变为空，但是参考答案认为边界条件就是两个数组都只有1个元素，并且每次的规模减半（也就是每次得出的
    子问题，AB长度都相同），这就和必定有一个数组为空而另一个不为空矛盾了。所以参考答案是错误的。
    """
    if n == 1:
        return (A[0]+B[0])/2.0
    mid = n//2
    m1 = A[mid]
    m2 = B[mid]
    if n % 2 == 0:
        pass


def MakeData():
    import random
    n = 10
    total = list(range(n))
    random.shuffle(total)
    A = total[:n//2]
    B = total[n//2:]
    A.sort()
    B.sort()
    return A, B


def Test():
    A, B = MakeData()
    print(A)
    print(B)
    FindMedian_Recur(A, B)


Test()
